/*
*
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 向右 或 向下 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

注意：任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

示例 1：

输入：dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
输出：7
解释：如果骑士遵循最佳路径：右 -> 右 -> 下 -> 下 ，则骑士的初始健康点数至少为 7 。
示例 2：

输入：dungeon = [[0]]
输出：1

提示：

m == dungeon.length
n == dungeon[i].length
1 <= m, n <= 200
-1000 <= dungeon[i][j] <= 1000

  - @author ala
  - @date 2024-09-20 14:57
*/
package main

import (
	"fmt"
	"math"
)

func main() {
	dungeon := [][]int{{-2, -3, 3}, {-5, -10, 1}, {10, 30, -5}}

	fmt.Println(calculateMinimumHP(dungeon))
}

/**
 *	1）公主反向找到勇者，告诉勇者需要携带多少血量
 *	2）dp[i][j]表示从(i,j)出发，需要携带的血量
 *		dp[i][j] = min(dp[i][j + 1, dp[i + 1][j]) - dungeon[i][j]
 *		如果 dp[i][j] < 0，说明这个位置可以白嫖，dp[i][j] = 1
 *	3）最后 dp[0][0] 就是答案
 */
func calculateMinimumHP(dungeon [][]int) int {
	M, N := len(dungeon), len(dungeon[0])

	dp := make([][]int, M)
	for i := range dp {
		dp[i] = make([]int, N)
	}

	for i := M - 1; i >= 0; i-- {
		for j := N - 1; j >= 0; j-- {
			if i == M-1 && j == N-1 {
				dp[i][j] = max(-dungeon[i][j]+1, 1)
				continue
			}

			left := math.MaxInt
			if j < N-1 {
				left = dp[i][j+1]
			}
			bottom := math.MaxInt
			if i < M-1 {
				bottom = dp[i+1][j]
			}
			dp[i][j] = max(min(left, bottom)-dungeon[i][j], 1)
		}
	}

	return dp[0][0]
}
